package DynamicProgramming;//有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
//
// 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下： 
//
// 
// 如果 x == y，那么两块石头都会被完全粉碎； 
// 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 
// 
//
// 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。 
//
// 
//
// 示例 1： 
//
// 
//输入：stones = [2,7,4,1,8,1]
//输出：1
//解释：
//组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
//组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
//组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
//组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
// 
//
// 示例 2： 
//
// 
//输入：stones = [31,26,33,21,40]
//输出：5
// 
//
// 示例 3： 
//
// 
//输入：stones = [1,2]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= stones.length <= 30 
// 1 <= stones[i] <= 100 
// 
// Related Topics 数组 动态规划 👍 358 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class lastStoneWeightII {
    public int lastStoneWeightII(int[] stones) {
        int len = stones.length;
        if(len<1){
            return len;
        }else if(len==1){
            return stones[0];
        }
        //题目要求最终最小，且选任意两个,且为正整数
//本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。
        int sum = Arrays.stream(stones).sum();
        int target = sum/2;  //总和的一半
        int[] dp = new int[target+1];
        //dp[j] 即是在最大负重j下背包中能存放的最大负重
        for (int i = 0; i < len; i++) {
            for (int j = target; j >= stones[i] ; j--) {
                dp[j] = Math.max(dp[j-stones[i]] + stones[i], dp[j]);
            }
        }
//        那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。
        return Math.abs((sum-dp[target])-dp[target]);

    }

    public int lastStoneWeightII2(int[] stones) {
        int len = stones.length;

        //最后一块石头的重量，其实是等分成两部分
        int sum = Arrays.stream(stones).sum();
        int target = sum/2;
        //dp[i][j] 表示当放入物品i时，且最大容量为j时，的最大重量
        int[][] dp = new int[len][target+1];
        //dp[i][0]默认初始化为0
        //dp[0][j]取决于stones[0]
        for (int j = stones[0]; j <= target; j++) {
            dp[0][j] = stones[0];
        }
        //状态转移,遍历物品 和 背包
        for(int i=1;i<len;i++){
            for(int j=1;j<=target;j++){
                //能放下物品i
                if(stones[i] <= j){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-stones[i]] + stones[i]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[len - 1][target]);
        return sum - dp[len-1][target] - dp[len-1][target];
    }
}
//leetcode submit region end(Prohibit modification and deletion)
